package com.example.dynamicprogramming41.practice;

/**
 * @description 动态规划-状态转移表法
 * @auther lijiewei
 * @date 2022/4/24 14:43
 */
public class DynamicProgrammingPractice {

    /**
     * 求最短路径
     * @param money
     * @return
     * @author lijiewei
     * @date   2022/4/12 17:46
     */
    public int minCoin(int money) {
        if (money==1 || money==3 || money==5) {
            return 1;
        }

        //构造一个 money*(money+1) 的二维表，x轴表示硬币数量，y轴表示拼凑的钱价值
        boolean[][] state = new boolean[money][money+1];
        if (money>=1) state[0][1] = true;
        if (money>=3) state[0][3] = true;
        if (money>=5) state[0][5] = true;

        //填充状态转移表
        for (int i = 1; i < money; i++) {
            for (int j = 1; j <= money; j++) {
                if(state[i-1][j]) {
                    if (j+1<=money) state[i][j+1]=true;
                    if (j+3<=money) state[i][j+3]=true;
                    if (j+5<=money) state[i][j+5]=true;
                    if (state[i][money]) return i+1;
                }
            }
        }
        return money;
    }
}
